package sort;

/**
 * 归并排序
 * @author aicview
 *
 */

public class Merge {
	
	private static Comparable [] assist;
	
	public static void sort(Comparable []arr) {
		//初始化辅助数组assist
		assist = new Comparable[arr.length];
		
		//定义一个low和high变量，记录数组中的最小索引和最大索引
		int low = 0;
		int high = arr.length-1;
		//调用sort重载方法完成数组arr中从low到high元素的排序
		sort(arr,low,high);
	} 
	
	public static void sort(Comparable [] arr,int low,int high) {
		//安全性检验
		if(high<=low) {
			return;
		}
		//对low到high之间的数据进行分组
		int mid = low+(high-low)/2;
		//分别对每一组数据进行排序
		sort(arr,low,mid);
		sort(arr,mid+1,high);
		//再把两个组中的数据进行归并
		merge(arr,low,mid,high);
		
		
	}
	
	public static void swap(Comparable[] arr,int i,int j) {
		Comparable temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
		
	}
	
	public static boolean less(Comparable a,Comparable b) {
		return a.compareTo(b)<0;
	}
	
	public static void merge(Comparable []arr,int low,int mid,int high) {
		//定义三个指针
		int i = low;
		int p1 = low;
		int p2 = mid+1;
		//遍历移动p1和p2指针，比较索引处的值，找出小的那一个，放到辅助数组中对应索引处
		while(p1<=mid&&p2<=high) {
			//比较对应索引处的值
			if(less(arr[p1],arr[p2])) {
				assist[i++] = arr[p1++];
			}else {
				assist[i++] = arr[p2++];
			}
		}
		//遍历，如果p1没有走完，那么顺序移动p1指针，把对应元素放到辅助数组的对应索引处
		while(p1<=mid) {
			assist[i++] = arr[p1++];
		}
		
		//遍历，如果p2没有走完，那么顺序移动p2指针，把对应元素放到辅助数组的对应索引处
		
		while(p2<=high) {
			assist[i++] = arr[p2++];
		}
	    //把辅助数组中的元素拷贝到原数组
		
		for(int index = low;index<=high;index++) {
			arr[index] = assist[index];
		}
		
		
		
		
	}
	

}
